package alogrithm.solution;

import alogrithm.structure.TreeNode;

/*
 * 在二元树中找出和为某一值的所有路径（树）
 题目：输入一个整数和一棵二元树。
 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
 打印出和与输入整数相等的所有路径。
 例如 输入整数22和如下二元树
 10  
 / /   
 5  12   
 /   /   
 4     7
 则打印出两条路径：10, 12和10, 5, 7。
 */
public class P4 {
	public static TreeNode findAllPathBySumUsingRecursive(int sum,TreeNode root)
	{
		if(root==null)return null;
		//get a new apposite path
		if(root.getValue().equals(sum)&&(root.getLeftChild()==root.getRightChild())&&root.getLeftChild()==null)
		{
			System.out.println();
			System.out.print(root.getValue()+"\t");
			return root;
		}
		else 
		{
			TreeNode left=findAllPathBySumUsingRecursive(sum-(Integer)(root.getValue()),root.getLeftChild());
			if(left!=null)
			{
				System.out.print(root.getValue()+"\t");	
			}
			TreeNode right=findAllPathBySumUsingRecursive(sum-(Integer)(root.getValue()),root.getRightChild());	
			if(right!=null)
			{
				System.out.print(root.getValue()+"\t");	
			}
			if(left!=null||right!=null)
			{
				return root;
			}
			else
				return null;
		}
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode n1=new TreeNode(4);
		TreeNode n2=new TreeNode(7);
		TreeNode n3=new TreeNode(1);
		TreeNode n5=new TreeNode(5,n1,n2);
		TreeNode n6=new TreeNode(11,n3,null);
		TreeNode n7=new TreeNode(10,n5,n6);
		findAllPathBySumUsingRecursive(22, n7);

	}

}
